<html>
<head><meta charset="utf-8"><title>Q: union find data structures · t-compiler/wg-nll · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/122657-t-compiler/wg-nll/index.html">t-compiler/wg-nll</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/122657-t-compiler/wg-nll/topic/Q.3A.20union.20find.20data.20structures.html">Q: union find data structures</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="154574232"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122657-t-compiler/wg-nll/topic/Q%3A%20union%20find%20data%20structures/near/154574232" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/122657-t-compiler/wg-nll/topic/Q.3A.20union.20find.20data.20structures.html#154574232">(Jan 07 2019 at 14:57)</a>:</h4>
<p>I have a question about chalk/polonius implomatation.</p>
<p>For Cargo's resolver, I have been looking into persistent union find data structures. The papers I am reading have had 2 examples of where these are useful:  for type resolution and for Prolog implementations. So my question is does chalk/polonius already have an implementation if not would a crate be useful for chalk/polonius?</p>



<a name="154575319"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122657-t-compiler/wg-nll/topic/Q%3A%20union%20find%20data%20structures/near/154575319" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/122657-t-compiler/wg-nll/topic/Q.3A.20union.20find.20data.20structures.html#154575319">(Jan 07 2019 at 15:10)</a>:</h4>
<p>A quote from the paper:<br>
"In Prolog, for example, variables of clauses correspond to elements of a set, and unifications imply disjoint set union operations. In this case, the availability of multiple versions of disjoint sets allows one to support backtracking and branching techniques, and to trace different program executions at the same time."</p>



<a name="154575686"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122657-t-compiler/wg-nll/topic/Q%3A%20union%20find%20data%20structures/near/154575686" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/122657-t-compiler/wg-nll/topic/Q.3A.20union.20find.20data.20structures.html#154575686">(Jan 07 2019 at 15:15)</a>:</h4>
<p>does it have to be persistent ? ena and rustc have a regular union-find IIRC</p>



<a name="154575858"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122657-t-compiler/wg-nll/topic/Q%3A%20union%20find%20data%20structures/near/154575858" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Eh2406 <a href="https://rust-lang.github.io/zulip_archive/stream/122657-t-compiler/wg-nll/topic/Q.3A.20union.20find.20data.20structures.html#154575858">(Jan 07 2019 at 15:17)</a>:</h4>
<p>For Cargo's resolver it would be nice. (I have already made the graph structure persistent, for a big performance win.)</p>



<a name="154575880"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122657-t-compiler/wg-nll/topic/Q%3A%20union%20find%20data%20structures/near/154575880" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/122657-t-compiler/wg-nll/topic/Q.3A.20union.20find.20data.20structures.html#154575880">(Jan 07 2019 at 15:17)</a>:</h4>
<p>(for polonius it's not immediately obvious to me <em>right now</em>, and the chalk team will be able to answer in the other stream, either niko or scalexm)</p>



<a name="154575950"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122657-t-compiler/wg-nll/topic/Q%3A%20union%20find%20data%20structures/near/154575950" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> davidtwco <a href="https://rust-lang.github.io/zulip_archive/stream/122657-t-compiler/wg-nll/topic/Q.3A.20union.20find.20data.20structures.html#154575950">(Jan 07 2019 at 15:18)</a>:</h4>
<p>(<a class="stream" data-stream-id="144729" href="/#narrow/stream/144729-wg-traits">#wg-traits</a>)</p>



<a name="154575993"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122657-t-compiler/wg-nll/topic/Q%3A%20union%20find%20data%20structures/near/154575993" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> lqd <a href="https://rust-lang.github.io/zulip_archive/stream/122657-t-compiler/wg-nll/topic/Q.3A.20union.20find.20data.20structures.html#154575993">(Jan 07 2019 at 15:18)</a>:</h4>
<p>(<span class="user-mention" data-user-id="116107">@davidtwco</span>  yeah eh2406 posted this question there already :)</p>



<a name="154576026"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/122657-t-compiler/wg-nll/topic/Q%3A%20union%20find%20data%20structures/near/154576026" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> davidtwco <a href="https://rust-lang.github.io/zulip_archive/stream/122657-t-compiler/wg-nll/topic/Q.3A.20union.20find.20data.20structures.html#154576026">(Jan 07 2019 at 15:19)</a>:</h4>
<p>Ah, <span class="emoji emoji-1f44d" title="thumbs up">:thumbs_up:</span></p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>